/**
 * Given a few dates, infer a periodic function that produces those dates and
 * possibly others.
 */
function inferDateSeries(dates, wkst) {
  wkst = wkst || 0;

  dates = dates.slice(0);
  dates.sort(function (a, b) { return a - b; });
  var firstDate = dates[0];
  var firstWeek = startOfWeek(firstDate, wkst);
  var nDates = dates.length;

  function mapDates(arr, f) {
    var iset = {};
    var out = [];
    for (var i = 0, n = arr.length; i < n; ++i) {
      var x = arr[i];
      x = f(x.getUTCFullYear(), x.getUTCMonth(), x.getUTCDate(), x.getUTCDay());
      var xi = +x;
      if (iset[xi] === iset) { continue; }
      out.push(x);
      iset[xi] = iset;
    }
    return out;
  }

  function minInterval(arr, toInt) {
    var n = arr.length;
    if (n < 2) { return 1; }
    var minInterval = Infinity;
    var last = toInt(arr[0]);
    for (var i = 1; i < n; ++i) {
      var next = toInt(arr[i]);
      var interval = next - last;
      if (interval < minInterval) { minInterval = interval; }
      last = next;
    }
    return minInterval;
  }

  function makeSet(arr) {
    var iset = {};
    for (var i = 0, n = arr.length; i < n; ++i) {
      iset[+arr[i]] = iset;
    }
    return iset;
  }

  // True if two objects have identical own keys with recursively similar
  // values as defined by ===.  Assumes a and b are acyclic.
  function objSimilar(a, b) {
    if (a === b) { return true; }
    if (!a || !b) { return false; }
    if (typeof a !== 'object' || typeof b !== 'object') { return false; }
    var hop = Object.hasOwnProperty;
    for (var k in a) {
      if (hop.call(a, k)) {
        if (!hop.call(b, k)) { return false; }
        if (!objSimilar(a[k], b[k])) { return false; }
      }
    }
    for (var k in b) {
      if (hop.call(b, k) && !hop.call(a, k)) { return false; }
    }
    return true;
  }

  function computeGreedySetCover(keyToSetIds, keyf) {
    function filter(arr, pred) {
      for (var i = 0, n = arr.length; i < n; ++i) {
        if (!pred(arr[i])) {
          var out = arr.slice(0, i);
          while (++i < n) {
            var x = arr[i];
            if (pred(x)) { out.push(x); }
          }
          return out;
        }
      }
      return arr;
    }

    var out = [];
    while (true) {
      var largestKey = void 0;
      var largestKeyCount = 0;
      for (var k in keyToSetIds) {
        if (Object.prototype.hasOwnProperty.call(keyToSetIds, k)) {
          var keyCount = keyToSetIds[k].length;
          if (keyCount > largestKeyCount) {
            largestKeyCount = keyCount;
            largestKey = k;
          }
        }
      }
      if (!largestKeyCount) { break; }
      out.push(keyf(largestKey));
      var covered = makeSet(keyToSetIds[largestKey]);
      delete keyToSetIds[largestKey];
      for (var k in keyToSetIds) {
        if (Object.prototype.hasOwnProperty.call(keyToSetIds, k)) {
          var setIds = filter(
            keyToSetIds[k], function (x) { return covered[x] !== covered; });
          if (setIds.length) {
            keyToSetIds[k] = setIds;
          } else {
            delete keyToSetIds[k];
          }
        }
      }
    }
    return out;
  }

  var years = mapDates(dates, function (y, _, _) { return date(y, 0, 1); });
  var months = mapDates(dates, function (y, m, _, _) { return date(y, m, 1); });
  var weeks = mapDates(
    dates, function (y, m, d, dow) {
      return date(y, m, d - ((7 + dow - wkst) % 7));
    });
  var days = mapDates(dates, function (y, m, d, _) { return date(y, m, d); });

  var daysOfWeek = [];
  var monthDaysToDateIndices = {};
  for (var i = 0, n = nDates; i < n; ++i) {
    var d = dates[i];
    daysOfWeek.push(d.getUTCDay());
    var dom = d.getUTCDate();
    var nDays = countDaysInMonth(d.getUTCFullYear(), d.getUTCMonth());
    var ndom = nDays - dom - 1;
    (monthDaysToDateIndices[dom] || (monthDaysToDateIndices[dom] = []))
      .push(i);
    (monthDaysToDateIndices[ndom] || (monthDaysToDateIndices[ndom] = []))
      .push(i);
  }
  daysOfWeek = uniqInts(daysOfWeek);
  var daysOfMonth = computeGreedySetCover(
    monthDaysToDateIndices, function (x) { return +x; });

  var lastCandidate = 0;
  var bestCandidate = void 0;
  var bestScore = -Infinity;

  var inputDateSet = makeSet(dates);
  function scoreOf(candidate) {
    var nMatches = 0;
    var series = dateSeries(firstDate, candidate);
    var generator = series.generator();
    try {
      for (var i = 0; i < nDates; ++i) {
        var d = generator();
        if (inputDateSet[+d] === inputDateSet) {
          ++nMatches;
        }
      }
    } catch (e) {
      return 0;
    }
    return nMatches / nDates;
  }

  function consider(candidates) {
    for (var i = 0, n = candidates.length; i < n; ++i) {
      if (bestScore === 1) { return; }
      var candidate = candidates[i];
      candidate.wkst = wkst;
      if (objSimilar(lastCandidate, candidate)) { continue; }
      lastCandidate = candidate;
      var score = scoreOf(candidate);
      if (bestScore < score) {
        bestCandidate = candidate;
        bestScore = score;
      }
    }
  }

  function considerForFreq(freq, interval) {
    consider([
      { freq: freq, interval: interval },
      { freq: freq, interval: interval, daysOfWeek: daysOfWeek },
      { freq: freq, interval: interval, daysOfMonth: daysOfMonth },
      { freq: freq, interval: interval, 
        daysOfMonth: daysOfMonth, daysOfWeek: daysOfWeek }]);
  }

  consider([{}]);

  if (years.length > 1) {
    var yearInterval = minInterval(
      years,
      function (d) { return d.getUTCFullYear(); });
    considerForFreq(FREQ_YEARLY, yearInterval);
  }

  if (months.length > 1) {
    var monthInterval = minInterval(
      months,
      function (d) { return d.getUTCFullYear() * 12 + d.getUTCMonth(); });
    considerForFreq(FREQ_MONTHLY, monthInterval);
  }

  if (weeks.length > 1) {
    var weekInterval = minInterval(
      weeks,
      function (d) { return (daysBetween(d, firstWeek) / 7) | 0; });
    considerForFreq(FREQ_WEEKLY, weekInterval);
  }

  {
    var dayInterval = minInterval(
      days, function (d) { return daysBetween(d, firstDate); });
    considerForFreq(FREQ_DAILY, dayInterval);
  }

  return {
    rule: bestCandidate,
    confidence: bestScore,
    dates: dates
  };
}
